package com.zk.algorithm.array;

import com.zk.algorithm.annotation.LeetCode;
import com.zk.algorithm.annotation.Medium;
import com.zk.algorithm.sort.QuickSort;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * 第 k 个最大值
 *
 * Input: [3,2,1,5,6,4] and k = 2
 * Output: 5
 *
 * https://leetcode.com/problems/kth-largest-element-in-an-array/discuss/60294/Solution-explained
 *
 * @author zk
 */
@Medium
@LeetCode("215")
public class KthLargestElementInAnArray {

    // ============================
    // - 排序
    // - nums[N - K]
    //
    // O(NlogN)
    // ============================

    public int findKthLargest1(int[] nums, int k) {
        final int N = nums.length;
        Arrays.sort(nums);
        return nums[N - k];
    }

    // ============================
    // - 维持一个最大容量为 k 的优先队列
    //
    // O(N) best case / O(N^2) worst case
    // ============================

    public int findKthLargest2(int[] nums, int k) {
        // 构建的是一个最小堆
        //
        // 堆顶是最小的值
        final PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (int val : nums) {
            pq.offer(val);

            // =========================
            // 维护一个大小为 k 的优先队列
            // =========================
            if (pq.size() > k) {
                pq.poll();
            }
        }

        return pq.peek();
    }

    // ============================
    // - 选择算法
    // - O(N)
    // ============================
    public int findKthLargest3(int[] nums, int k) {
        k = nums.length - k;

        int lo = 0;
        int hi = nums.length - 1;

        while (lo < hi) {
            final int j = QuickSort.partition(nums, lo, hi);

            // ==================================================
            //                     j           k
            //                     ↓           ↓
            // [小于 nums[j] 的| nums[j] |大于 nums[j] 的]
            // ==================================================
            if (j < k) {
                lo = j + 1;
            } else if (j > k) {
                // ==================================================
                //         k           j
                //         ↓           ↓
                // [小于 nums[j] 的| nums[j] |大于 nums[j] 的]
                // ==================================================
                hi = j - 1;
            } else {
                break;
            }
        }

        return nums[k];
    }

    // ============================
    // - 选择算法优化 (随机 shuffle 数组)
    // - O(N)
    // ============================

    public int findKthLargest4(int[] nums, int k) {
        ShuffleArray.shuffle(nums);
        return findKthLargest3(nums, k);
    }

}
